1
Condiciones de Optimalidad para Restricciones de Igualdad
MATH008Lesson 10
00:00
Imagina un sistema físico, como una cadena colgante, buscando su estado de energía más bajo. Si los extremos están fijos, el sistema no puede moverse libremente. La optimalidad se alcanza cuando las fuerzas internas (el gradiente de la energía potencial) quedan perfectamente equilibradas por las fuerzas de tensión ejercidas por las restricciones. En la optimización convexa, este equilibrio queda capturado por las condiciones KKT para restricciones de igualdad.

La Geometría de la Factibilidad

Para un problema convexo con restricciones de igualdad $Ax=b$, un vector $v \in \mathbf{R}^n$ es una dirección factible si $Av = 0$. Esto significa que moverse en la dirección $v$ mantiene la restricción: $A(x+v) = b$ si $Ax=b$.

Para que $x^*$ sea óptimo, la derivada direccional $\nabla f(x^*)^T v$ debe ser cero para todas las direcciones factibles $v$ en el núcleo $\mathcal{N}(A)$. Esto implica que el gradiente $\nabla f(x^*)$ debe ser ortogonal a $\mathcal{N}(A)$, lo que nos lleva a la existencia de multiplicadores de Lagrange.

La Condición de Optimalidad

Un punto $x^*$ es óptimo si y solo si existe un vector $\nu^* \in \mathbb{R}^p$ tal que:

$\nabla f(x^*) + A^T \nu^* = 0$

Esto forma un sistema de ecuaciones lineales que caracteriza el equilibrio entre la disminución del objetivo y la superficie de restricción.

El Gradiente Proyectado

La proyección euclídea del gradiente negativo $-\nabla f(x)$ sobre el núcleo $\mathcal{N}(A)$ viene dada por:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

Este vector representa la dirección descendente "mejor" factible. Es crucial que $x$ sea óptimo si y solo si $\Delta x_{\text{pg}} = 0$.

El Sistema KKT y las Propiedades Matriciales

Podemos resolver simultáneamente el paso de Newton y las variables duales usando el sistema por bloques:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

Nota sobre las propiedades espectrales de la matriz: La matriz KKT es simétrica pero indefinida. Si la matriz es no singular, tiene exactamente $n$ valores propios positivos y $p$ negativos. Esto implica que el punto óptimo $(x^*, \nu^*)$ es un punto de silla de la lagrangiana $L(x, \nu) = f(x) + \nu^T(Ax-b)$, más que un mínimo local simple en el espacio primal-dual combinado.

🎯 Principio Fundamental
La optimalidad en problemas con restricciones de igualdad requiere que el gradiente sea ortogonal al núcleo de la restricción. Esto nos permite interpretar el paso de Newton como la solución de una aproximación lineal de las condiciones KKT.